Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11846 - Finding Seats Again / 11846.cpp
blob060aa55a856b2ff89e288c3455cd2f69ff276942
1 // This times out!
2 using namespace std;
3 #include <algorithm>
4 #include <iostream>
5 #include <iterator>
6 #include <numeric>
7 #include <sstream>
8 #include <fstream>
9 #include <cassert>
10 #include <climits>
11 #include <cstdlib>
12 #include <cstring>
13 #include <string>
14 #include <cstdio>
15 #include <vector>
16 #include <cmath>
17 #include <queue>
18 #include <deque>
19 #include <stack>
20 #include <list>
21 #include <map>
22 #include <set>
24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
26 #define D(x) cout << #x " is " << x << endl
28 const int MAXN = 20;
29 const int MAXK = 27;
31 struct region {
32 short r1, r2, c1, c2;
33 region() {}
34 region(short r1, short r2, short c1, short c2) : r1(r1), r2(r2), c1(c1), c2(c2) {}
37 struct cell {
38 short r, c;
39 cell() {}
40 cell(short r, short c) : r(r), c(c) {}
43 int N, K;
44 char mat[MAXN][MAXN];
45 cell leaders[MAXK];
46 int people[MAXK];
47 vector< region > options[MAXK];
49 inline bool valid(const region& r) {
50 return (0 <= r.r1 and r.r1 <= r.r2 and r.r2 < N and
51 0 <= r.c1 and r.c1 <= r.c2 and r.c2 < N);
54 inline bool containsCell(const region &rg, int r, int c) {
55 return rg.r1 <= r and r <= rg.r2 and rg.c1 <= c and c <= rg.c2;
58 inline bool containsDifferentLetter(const region &r, char letter) {
59 //assert(valid(r));
60 for (int i = r.r1; i <= r.r2; ++i) {
61 for (int j = r.c1; j <= r.c2; ++j) {
62 if (mat[i][j] != '.' and mat[i][j] != letter) return true;
65 return false;
68 inline bool sameLetterOutsideRegion(const region &r, char letter) {
69 for (int i = 0; i < N; ++i) {
70 for (int j = 0; j < N; ++j) {
71 if (containsCell(r, i, j)) continue;
72 if (mat[i][j] != '.' and mat[i][j] == letter) return true;
75 return false;
79 inline bool containsEmptyCell(const region &r) {
80 //assert(valid(r));
81 for (int i = r.r1; i <= r.r2; ++i) {
82 for (int j = r.c1; j <= r.c2; ++j) {
83 if (mat[i][j] == '.') return true;
86 return false;
90 inline void fillRegion(const region &r, char letter) {
91 //assert(valid(r));
92 for (int i = r.r1; i <= r.r2; ++i) {
93 for (int j = r.c1; j <= r.c2; ++j) {
94 mat[i][j] = letter;
99 bool deduceFixedPositions() {
100 bool changed = false;
102 for (int k = 0; k < K; ++k) {
103 int oldOptionsSize = options[k].size();
105 options[k].clear();
107 int size = people[k];
108 for (int width = 1; width <= size; ++width) {
109 if (size % width != 0) continue;
110 int height = size / width;
111 char leaderLetter = mat[leaders[k].r][leaders[k].c];
113 for (int i = max(0, leaders[k].r - height + 1); i + height - 1 < N and i <= leaders[k].r; ++i) {
114 for (int j = max(0, leaders[k].c - width + 1); j + width - 1 < N and j <= leaders[k].c; ++j) {
115 region r(i, i + height - 1, j, j + width - 1);
116 assert(valid(r));
117 assert(containsCell(r, leaders[k].r, leaders[k].c));
118 //printf("considering region <r1=%d, r2=%d, c1=%d, c2=%d> for leader %d\n", r.r1, r.r2, r.c1, r.c2, k);
119 if (containsDifferentLetter(r, leaderLetter)) {
120 //printf("discarding because it also has a different letter\n");
121 continue;
123 if (sameLetterOutsideRegion(r, leaderLetter)) {
124 //printf("discarding because this letter is also outside this region\n");
125 continue;
127 options[k].push_back( r );
132 if (oldOptionsSize != options[k].size()) {
133 changed = true;
136 if (options[k].size() == 1 and containsEmptyCell(options[k][0])) {
137 fillRegion(options[k][0], 'A' + k);
138 changed = true;
141 //for (int i = 0; i < options[k].size(); ++i){ region r = options[k][i]; printf("There's a possible region for leader %d at <r1=%d, r2=%d, c1=%d, c2=%d>\n", k, r.r1, r.r2, r.c1, r.c2); }
144 //for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { printf("%c", mat[i][j]); } puts(""); }
146 if (changed) return true;
148 // Place a letter where there's only a possible leader that covers that cell
149 for (int i = 0; i < N; ++i) {
150 for (int j = 0; j < N; ++j) {
151 if (mat[i][j] != '.') continue;
152 int leaderThatContainsMe = -1; int numberOfLeadersThatContainMe = 0;
153 for (int k = 0; k < K; ++k) {
154 for (int o = 0; o < options[k].size(); ++o) {
155 if (containsCell(options[k][o], i, j)) {
156 leaderThatContainsMe = k;
157 numberOfLeadersThatContainMe++;
158 break;
162 //printf("cell <%d, %d>: number of leaders that contain me = %d\n", i, j, numberOfLeadersThatContainMe);
163 //assert(numberOfLeadersThatContainMe > 0);
164 if (numberOfLeadersThatContainMe == 1) {
165 mat[i][j] = leaderThatContainsMe + 'A';
166 changed = true;
171 //for (int k = 0; k < K; ++k) for (int i = 0; i < options[k].size(); ++i){ region r = options[k][i]; printf("There's a possible region for leader %d at <r1=%d, r2=%d, c1=%d, c2=%d>\n", k, r.r1, r.r2, r.c1, r.c2); }
173 if (changed) return true;
175 return false;
178 bool cellWith0CoveringRegions() {
179 for (int i = 0; i < N; ++i) {
180 for (int j = 0; j < N; ++j) {
181 for (int k = 0; k < K; ++k) {
182 char letter = 'A' + k;
183 for (int o = 0; o < options[k].size(); ++o) {
184 const region &r = options[k][o];
185 if (!containsCell(r, i, j)) continue;
186 if (sameLetterOutsideRegion(r, letter)) continue; // can't take this one
187 if (containsDifferentLetter(r, letter)) continue;
188 return false;
193 return true;
196 bool backtrack(int k, int placed) {
197 //printf("k = %d, K = %d\n", k, K);
198 //for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { printf("%c", mat[i][j]); } puts(""); }
200 if (k == K or placed == k) {
201 // Found solution!
202 for (int i = 0; i < N; ++i) {
203 for (int j = 0; j < N; ++j) {
204 putchar(mat[i][j]);
206 putchar('\n');
208 return true;
212 if (cellWith0CoveringRegions()) return false;
214 //for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { printf("%c", mat[i][j]); } puts(""); }
216 char letter = mat[leaders[k].r][leaders[k].c];
218 for (int o = 0; o < options[k].size(); ++o) {
219 const region &r = options[k][o];
220 // let's take this region
221 if (sameLetterOutsideRegion(r, letter)) continue; // can't take this one
222 if (containsDifferentLetter(r, letter)) continue;
224 vector< cell > changed;
225 for (int i = r.r1; i <= r.r2; ++i) {
226 for (int j = r.c1; j <= r.c2; ++j) {
227 assert(mat[i][j] == '.' or mat[i][j] == letter);
228 if (mat[i][j] == '.') {
229 changed.push_back ( cell(i, j) );
230 mat[i][j] = letter;
234 if (backtrack(k + 1, placed + 1)) return true;
236 for (int c = 0; c < changed.size(); ++c) {
237 mat[changed[c].r][changed[c].c] = '.';
240 return false;
243 int main(){
244 while (scanf("%d %d", &N, &K) == 2) {
245 int currentLeader = 0;
246 for (int i = 0; i < N; ++i) {
247 for (int j = 0; j < N; ++j) {
248 char c = getchar(); while (isspace(c)) c = getchar();
249 mat[i][j] = c;
250 if (isdigit(c)) {
251 leaders[currentLeader] = cell(i, j);
252 people[currentLeader] = c - '0';
253 options[currentLeader].clear();
254 mat[i][j] = 'A' + currentLeader;
255 currentLeader++;
260 // sort leaders by size
261 for (int i = 0; i < K; ++i) {
262 for (int j = i + 1; j < K; ++j) {
263 if (people[j] > people[i]) {
264 swap(mat[leaders[i].r][leaders[i].c], mat[leaders[j].r][leaders[j].c]);
265 swap(leaders[i], leaders[j]);
266 swap(people[i], people[j]);
271 //for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { printf("%c", mat[i][j]); } puts(""); }
273 // for (int i = 0; i < K; ++i) {
274 // printf("There's a leader at <%d, %d> of size %d\n", leaders[i].r, leaders[i].c, people[i]);
275 // }
277 bool changed = true;
278 while (changed) {
279 changed = deduceFixedPositions();
282 // for (int i = 0; i < N; ++i) {
283 // for (int j = 0; j < N; ++j) {
284 // printf("%c", mat[i][j]);
285 // }
286 // printf("\n");
287 // }
288 int count = 0;
289 for (int k = 0; k < K; ++k) {
290 int seen = 0;
291 for (int i = 0; i < N; ++i) {
292 for (int j = 0; j < N; ++j) {
293 seen += (mat[i][j] == 'A' + k);
296 count += (seen == people[k]);
298 assert(backtrack(0, count));
300 return 0;